package main

import "fmt"

// 如何求字符串的编辑距离

func main() {
	s1 := "bciln"
	s2 := "fciling"
	fmt.Println(edit(s1, s2, 1))
}

// 参数 replaceWight 用来表示替换操作与插入删除操作相比的倍数
func edit(s1, s2 string, replaceWight int) int {
	if s1 == s2 {
		return 0
	}

	if s1 == "" {
		return len(s2)
	}
	if s2 == "" {
		return len(s1)
	}

	len1, len2 := len(s1), len(s2)

	D := make([][]int, len1+1)
	for i := range D {
		D[i] = make([]int, len2+1)
	}
	for i := 0; i < len1+1; i++ {
		D[i][0] = i
	}
	for i := 0; i < len2+1; i++ {
		D[0][i] = i
	}

	for i := 1; i < len1+1; i++ {
		for j := 1; j < len2+1; j++ {
			if s1[i-1] == s2[j-1] {
				D[i][j] = min3(D[i-1][j]+1, D[i][j-1]+1, D[i-1][j-1])
			} else {
				D[i][j] = min3(D[i-1][j]+1, D[i][j-1]+1, D[i-1][j-1]+replaceWight)
			}
		}
	}

	for i := 0; i < len1+1; i++ {
		for j := 0; j < len2+1; j++ {
			fmt.Print(D[i][j], " ")
		}
		fmt.Println()
	}

	return D[len1][len2]
}

func min3(a, b, c int) int {
	if a <= b && a <= c {
		return a
	} else if b <= c {
		return b
	} else {
		return c
	}
}
